package g

/*
 * @lc app=leetcode.cn id=543 lang=golang
 *
 * [543] 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
这条路径可能穿过也可能不穿过根结点。
*/

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
//          1
//         / \
//        2   3
//       / \
//      4   5
//     /     \
//    6       8
//     \       \
//      7       9
// return
func diameterOfBinaryTree(root *TreeNode) int {
	_, maxDep := maxHeight(root, 0)
	return maxDep
}

//树的高度
func maxHeight(root *TreeNode, curMaxDiameter int) (height int, maxDiameter int) {
	if root == nil {
		maxDiameter = curMaxDiameter
		height = 0
		return
	}
	lHeight, curMaxDiameter := maxHeight(root.Left, curMaxDiameter)
	rHeight, curMaxDiameter := maxHeight(root.Right, curMaxDiameter)
	maxDiameter = maxInt(curMaxDiameter, lHeight+rHeight)
	height = maxInt(lHeight, rHeight) + 1
	return
}

func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end
